/*
 * graph.h
 *
 *  Created on: May 28, 2012
 *      Author: nogah
 */


#ifndef GRAPH_H
#define GRAPH_H
#include <list>
#include <algorithm>
#include <map>
#include <iostream>
#include <queue>
#include <climits>

#define IS_BETTER 1
#define IS_EQUAL 0
#define IS_WORSE -1

#define FIRST_NODE -1
#define LAST_NODE -2147483647
#define DELETED_NODE 0

class WeightedEdge;

class Node {
public:
  int id;
  std::list<std::list<int>::iterator> pos;
  std::map<int, WeightedEdge*> nexts;
  Node() { }
  Node(int id, std::list<int>::iterator it) : id(id) { pos.push_back(it); }
  int getId() const {
    return id;
  }
  void addNext(Node*);
  void addPos(std::list<int>::iterator it);
  void removePos(std::list<int>::iterator it);
  friend std::ostream& operator<< (std::ostream& stream, Node& node);
  void deleteEdge(Node *n);
};

class WeightedEdge {
public:
  Node *toNode;
  int multiplicity;
  WeightedEdge(Node *node) : toNode(node){
    multiplicity = 1;
  }

  bool operator==(const WeightedEdge& o) {
    return o.toNode->id == toNode->id;
  }

  void incMultiplicity() {
    multiplicity++;
  }
  friend std::ostream& operator<< (std::ostream& stream, WeightedEdge& edge);

};

struct QueueEdge {
public:
  QueueEdge(Node *from, int to) : from(from), to(to) {  }
  Node* from;
  int to;
};

class Path {
  std::list<int>::iterator startIt, endIt;
  std::list<int> path;
  std::priority_queue<int> multiplicityQ;
  std::list<QueueEdge*> edges;
public:
  std::list<int>& getPath() {
    return path;
  }
  std::list<QueueEdge*>& getEdges() {
    return edges;
  }
  std::priority_queue<int>& getMultiplicityQueue() {
    return multiplicityQ;
  }
  void push_back(int next) {
    path.push_back(next);
  }
  void push_front(int next) {
    path.push_front(next);
  }
  void getPathMultiplicity(std::priority_queue<int>& q);
  int comparePath(Path& p2);
  void print();
  void incPathMultiplicity();
  void trimFromEndTo(int id);
  void trimFromStartTo(int id);
  size_t length() { return path.size(); }
  bool contain(int n);
  void setStartIt(std::list<int>::iterator it) {
    startIt = it;
  }
  void setEndIt(std::list<int>::iterator it) {
    endIt = it;
  }
  std::list<int>::iterator& getStartIt() {
    return startIt;
  }
  std::list<int>::iterator& getEndIt() {
    return endIt;
  }

};


bool Path::contain(int n) {
  for (auto it = path.begin(); it != path.end(); it++) {
    if (*it == n) {
      return true;
    }
  }
  return false;
}

void Path::print() {
  std::cerr << "-- Path --\n";
  for (auto it = path.begin(); it != path.end(); it++) {
    std::cerr << *it << std::endl;
  }
  std::cerr << "\n";
}

int Path::comparePath(Path& p2) {
  std::priority_queue<int> &q1 = getMultiplicityQueue();
  std::priority_queue<int> &q2 = p2.getMultiplicityQueue();

  while (!q1.empty() && !q2.empty()) {
    if (q1.top() > q2.top()) return IS_BETTER;
    else if (q1.top() < q2.top()) return IS_WORSE;
    q1.pop();
    q2.pop();
  }
  if (q1.empty() && !q2.empty()) return IS_WORSE;
  if (!q1.empty() && q2.empty()) return IS_BETTER;

  return IS_EQUAL;
}

void Path::incPathMultiplicity() {
  // increase multiplicity of all edge in path
  //std::cout << "multi size: " << edges.size() << std::endl;
  for (std::list<QueueEdge*>::iterator it = edges.begin(); it != edges.end(); it++) {
    (*it)->from->nexts[(*it)->to]->incMultiplicity();
    //std::cout << "multi: " << (*it)->from->nexts[(*it)->to]->multiplicity << std::endl;
  }
}

void Path::trimFromEndTo(int id) {
  //print();
  while (*(path.rbegin()) != id) {
    //std::cerr << "delete from path: " << *(path.rend());
    path.pop_back();
    --endIt;
  }
}

void Path::trimFromStartTo(int id) {
  //print();
  while (*(path.begin()) != id) {
    //std::cerr << "delete from path: " << *(path.rend());
    path.pop_front();
    ++startIt;
  }
}

void Node::addNext(Node *o) {
  std::map<int, WeightedEdge*>::iterator iNode = nexts.find(o->getId());
  if (iNode == nexts.end()) {
    nexts[o->getId()] = new WeightedEdge(o);
  }
  else {
    nexts[o->getId()]->incMultiplicity();
  }
  //nextPos.push_back(o->pos.back());
}

void Node::addPos(std::list<int>::iterator it) {
  pos.push_back(it);
}


void Node::removePos(std::list<int>::iterator it) {
  pos.remove(it);
}

void Node::deleteEdge(Node *n) {
  auto it = nexts.find(n->getId());
  if (it->second->multiplicity == 1) {
    nexts.erase(it);
    // TODO delete nextEdge here or not?
  }
  else {
    it->second->multiplicity--;
  }
}

std::ostream& operator<< (std::ostream& stream, WeightedEdge& edge) {
  stream << "\t to " << edge.toNode->id;
  stream << " with multiplicity " << edge.multiplicity << "\n";
  return stream;
}


std::ostream& operator<< (std::ostream& stream, Node& node) {
  stream << "Node " << node.id << " at ";
  stream << "< ";
//  for (std::list<int>::iterator it = node.pos.begin();
//      it != node.pos.end();
//      it++) {
//    stream << *it << " ";
//  }
  stream << " >\n";

  for (std::map<int, WeightedEdge*>::iterator it = node.nexts.begin();
      it != node.nexts.end();
      it++) {
    stream << *(it->second);
  }
  return stream;
}

std::ostream& operator<< (std::ostream& stream, std::list<int> &nodes) {
  for (auto it = nodes.begin(); it != nodes.end(); ++it) {
    stream << *it << std::endl;
  }
  return stream;
}

#endif


